﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

//将两个升序链表合并为一个新的 升序 链表并返回
//思路：
// 前提：有两个升序链表（先创建两个升序链表）
// 1.利用哨兵位创建一个空链表
// 2.循环比较，将小的数尾插到新链表
// 3.当一方遍历完，结束循环，将另一方其余节点尾插
// 4.销毁哨兵位，返回空间
typedef struct ListNode {
	int val;
	struct ListNode* next;
}LN;
// 创建节点
LN* buynode(int x)
{
	LN* newnode = (LN*)malloc(sizeof(LN));
	if (newnode == NULL)
	{
		perror("malloc:");
		exit(1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
// 创建链表
LN* list(int n)
{
	int x = 0;
	LN* newnode = buynode(-1);
	LN* pucr = newnode;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &x);
		pucr->next = buynode(x);
		pucr = pucr->next;
	}
	LN* ret = newnode->next;
	free(newnode);
	newnode = ret;
	return newnode;
}
void prinnode(LN* p)
{
	while (p)
	{
		printf("%d ", p->val);
		p = p->next;
	}
	printf("\n");
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}

	LN* newhead = buynode(-1);
	LN* pucr = newhead;
	LN* p1 = list1;
	LN* p2 = list2;
	while (p1 && p2)
	{
		if (p1->val > p2->val)
		{
			pucr->next = p2;
			p2 = p2->next;
			pucr = pucr->next;
		}
		else
		{
			pucr->next = p1;
			p1 = p1->next;
			pucr = pucr->next;
		}
	}
	if (p1)
	{
		pucr->next = p1;
	}
	else
	{
		pucr->next = p2;
	}
	LN* ret = newhead->next;
	free(newhead);
	newhead = NULL;
	return ret;
}
int main()
{
	int n = 3;
	LN* p1 = list(n);
	prinnode(p1);
	LN* p2 = list(n);
	prinnode(p2);
	LN* p3 = mergeTwoLists(p1, p2);
	prinnode(p3);


	return 0;
}

